Insertion works like searching, but its goal is to find an empty spot where the new node should attach.
- The insert function traverses the tree until it finds a None child pointer.
- When it finds that empty child it creates a new Node and attaches it there.
- If the key already exists, the loop stops and the tree remains unchanged.
# Iterative insertion into the BST.
def insert(root, key):
"""Inserts a key into the BST iteratively."""
if root is None:
# The tree is empty.
return Node(__________)
current = root
while True:
if key < current.key:
# Go left. If empty, this is our spot!
if current.left is None:
current.left = Node(__________)
break
else:
current = current.left
elif key > current.key:
# Go right. If empty, this is our spot!
if current.right is None:
current.right = Node(__________)
break
else:
current = current.right
else:
# Key already exists, do nothing.
break
return root
Copied!